//一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出
//这个数字。 
//
// 
//
// 示例 1: 
//
// 输入: [0,1,3]
//输出: 2
// 
//
// 示例 2: 
//
// 输入: [0,1,2,3,4,5,6,7,9]
//输出: 8 
//
// 
//
// 限制： 
//
// 1 <= 数组长度 <= 10000 
// Related Topics 位运算 数组 哈希表 数学 二分查找 
// 👍 160 👎 0


package leetcode.editor.cn1;
//Java：0～n-1中缺失的数字

/**
 * 一个长度为n-1的递增排序数组中的所有数字都是唯一的，
 * 并且每个数字都在范围0～n-1之内。在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。
 *
 */
public class QueShiDeShuZiLcof {
    public static void main(String[] args) {
        Solution solution = new QueShiDeShuZiLcof().new Solution();
        // TO TEST
        System.out.println(solution.missingNumber(new int[]{1}));
    }
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int missingNumber(int[] nums) {
        if (nums.length == 0)
            return -1;
        int[] dp = new int[nums.length + 1];
        int i = 0, j = 0;
        int nlen = nums.length;
        for (i = 0; i < nlen; i++) {
            dp[nums[i]] = 1;
        }
        for (j = 0; j <= nlen; j++) {
            if (dp[j] == 0)
                return j;
        }
        return -1;
    }
}
    //leetcode submit region end(Prohibit modification and deletion)

}
